package com.demo.datastructure.reorder.mergeSort;

import com.demo.datastructure.reorder.Example;

/**
 * @author ljr
 * @version 1.0
 * @description: TODO
 * @date 2021/10/1 12:16
 */
public class SimpleMergeSort3 implements Example {

    @Override
    public void sort(Comparable[] a, int low, int high) {
        if(low <= high)  return;
        int mid = low + (high - low >> 1);
        sort(a, low, mid);
        sort(a, mid+1, high);
        merge(a, low, mid, high);
    }

    private void merge(Comparable[] a, int low, int mid, int high) {
        Comparable[] newA = new Comparable[high-mid+1];
        int l =  low, h = mid+1;
        for(int i = 0; i <newA.length; i++){
            if(l > mid) newA[i] = a[h++];
            else if(h > high) newA[i] = a[l++];
            else if(less(a[l], a[h])) newA[i] =  a[l++];
            else  newA[i] = a[h++];
        }

        for(int i = 0; i <newA.length; i++){
            a[low++] = newA[i];
        }

    }
}
